package com.mj.listen2._03_图;

import java.util.*;

public class ListGraph<V, E> implements Graph<V, E> {

    /**
     * 节点类
     */
    private static class Vertex<V, E> {
        // 值与节点一一对应
        V value;

        // 进来的边，使用set集合保存所有进来的边。set原因查找、增删都比较快
        Set<Edge<V, E>> inEdges = new HashSet<>();

        // 出去的边，使用set集合保存所有出去的边
        Set<Edge<V, E>> outEdges = new HashSet<>();

        // 构造方法，创建一个 Vertex 对象就传入对应的值
        public Vertex(V value) {
            this.value = value;
        }

        // 如果两个顶点的值是一样的，这两个顶点就是相等的。
        @Override
        public boolean equals(Object obj) {
            return Objects.equals(value, ((Vertex<V, E>) obj).value);
        }

        @Override
        public int hashCode() {
            return value == null ? 0 : value.hashCode();
        }

        @Override
        public String toString() {
            return value == null ? "null" : value.toString();
        }
    }

    /**
     * 边类
     */
    private static class Edge<V, E> {
        // 出发点
        Vertex<V, E> from;
        // 到达点
        Vertex<V, E> to;
        // 权值
        E weight;

        // 创建一个边对象，需要传入该边的两个顶点，表示从哪到哪(出发点、到达点)
        public Edge(Vertex<V, E> from, Vertex<V, E> to) {
            this.from = from;
            this.to = to;
        }

        /*****  实现 equals 和 hashCode 原因在于在 HashSet 中做判断的时候根据这两个方法做判断的 *****/
        @Override
        public boolean equals(Object obj) {
            Edge<V, E> edge = (Edge<V, E>) obj;
            // 如果两条边的出发点和到达点都是一个，说明这两天边相等
            return Objects.equals(from, edge.from) && Objects.equals(to, edge.to);
        }

        @Override
        public int hashCode() {
            // 与 equals 方法对应，涵盖 from 和 to。
            return from.hashCode() * 31 + to.hashCode();
        }

        @Override
        public String toString() {
            return "Edge [from=" + from + ", to=" + to + ", weight=" + weight + "]";
        }
    }

    // 传入的V与顶点类Vertex的映射，内部使用map结构
    private Map<V, Vertex<V, E>> vertices = new HashMap<>();
    // 边的Set集合
    private Set<Edge<V, E>> edges = new HashSet<>();

    @Override
    public int edgeSize() {
        return edges.size();
    }

    @Override
    public int verticesSize() {
        return vertices.size();
    }

    @Override
    public void addVertex(V v) {
        if (vertices.containsKey(v)) return;
        vertices.put(v, new Vertex<>(v));
    }

    @Override
    public void addEdge(V from, V to) {
        addEdge(from, to, null);
    }

    @Override
    public void addEdge(V from, V to, E weight) {
        // 根据传入的参数from找到起点,如果不存在则创建
        Vertex<V, E> fromVertex = vertices.get(from);
        if (fromVertex == null) {
            fromVertex = new Vertex<>(from);
            vertices.put(from, fromVertex);
        }

        // 根据传入的参数to找到终点,如果不存在则创建
        Vertex<V, E> toVertex = vertices.get(to);
        if (toVertex == null) {
            toVertex = new Vertex<>(to);
            vertices.put(to, toVertex);
        }

        // 根据出发点与终点,创建边
        Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
        edge.weight = weight; // 有权值则加上权值,无权值则为null

        // 不管原来是否存在,都先删除此边,再添加进去
        if (fromVertex.outEdges.remove(edge)) {
            toVertex.inEdges.remove(edge);
            edges.remove(edge);
        }
        fromVertex.outEdges.add(edge);
        toVertex.inEdges.add(edge);
        edges.add(edge);
    }

    @Override
    public void removeVertex(V v) {
        // 要被删除的节点
        Vertex<V, E> removeVertex = vertices.remove(v);
        if (null == removeVertex) return;
        // 存在节点

        // 删除所有与 removeVertex 相关联的边，以及边另一头节点相应的信息()
        // 删除出去的边。先遍历到边，然后把边信息删除掉
        for (Iterator<Edge<V, E>> iterator = removeVertex.outEdges.iterator(); iterator.hasNext(); ) {
            Edge<V, E> edge = iterator.next(); // 遍历到的该点出去的边
            edge.to.inEdges.remove(edge);// 找到该边终点的节点，并将该边从终点节点的inEdges中删除掉
            // 将当前遍历到的元素edge从集合removeVertex.outEdges中删掉
            iterator.remove();
            // 图维护的边也删除掉
            edges.remove(edge);
        }

        // 删除进来的边
        for (Iterator<Edge<V, E>> iterator = removeVertex.inEdges.iterator(); iterator.hasNext(); ) {
            Edge<V, E> edge = iterator.next(); // 遍历到的该点进来的边
            // 找到该边起点的节点，并将该边从起点节点的outEdges中删除掉
            edge.from.outEdges.remove(edge);
            // 将当前遍历到的元素edge从集合removeVertex.inEdges中删掉
            iterator.remove();
            // 图维护的边也删除掉
            edges.remove(edge);
        }
    }

    @Override
    public void removeEdge(V from, V to) {
        // 不包含顶点则返回null
        Vertex<V, E> fromVertex = vertices.get(from);
        if (fromVertex == null) return;

        Vertex<V, E> toVertex = vertices.get(to);
        if (toVertex == null) return;

        // 说明包含顶点
        // 根据起点和终点获得边,然后删除。顶点存在，但是边不一定存在
        Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
        // 该边需要从 from 节点的出去的边集合(outEdges)里面删除
        if (fromVertex.outEdges.remove(edge)) {// 存在边才去删除
            // 该边需要从 to 节点的进来的边集合(inEdges)里面删除
            toVertex.inEdges.remove(edge);
            // 该边需要从图维护的整体边集合里面移除
            edges.remove(edge);
        }
    }

    public void print() {
        System.out.println("[顶点]-------------------");
        vertices.forEach((V v, Vertex<V, E> vertex) -> {
            // 当前顶点
            System.out.println(v);
            System.out.println("out-----------");
            // 该顶点所有的出去的边
            System.out.println(vertex.outEdges);
            System.out.println("int-----------");
            // 该顶点所有进来的边
            System.out.println(vertex.inEdges);
        });
        System.out.println("[边]-------------------");
        edges.forEach((Edge<V, E> edge) -> {
            System.out.println(edge);
        });
    }

    @Override
    public void bfs(V begin, VertexVisitor<V> visitor) {
        if (visitor == null) return;
        // 找出这个节点
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return;

        // 存放已经访问过的节点
        Set<Vertex<V, E>> visitedVertices = new HashSet<>();
        Queue<Vertex<V, E>> queue = new LinkedList<>();
        // 入队
        queue.offer(beginVertex);
        // 每次入队的时候，都把最新的节点添加到 visitedVertices 中
        visitedVertices.add(beginVertex);

        while (!queue.isEmpty()) {
            Vertex<V, E> vertex = queue.poll();
            visitor.visit(vertex.value);

            for (Edge<V, E> edge : vertex.outEdges) {
                // 如果集合中已经记录该顶点,说明已经访问过,跳过进行下一轮
                if (visitedVertices.contains(edge.to)) continue;
                // 该节点入队
                queue.offer(edge.to);
                // 往集合中也添加该节点
                visitedVertices.add(edge.to);
            }
        }
    }

    /**
     * 深度优先遍历非递归实现
     *
     * @param begin 从哪个点开始进行深度优选搜索
     */
    @Override
    public void dfs(V begin, VertexVisitor<V> visitor) {
        if (visitor == null) return;
        // 找出这个节点
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return;

        // 非递归实现深度优先遍历
        // 存放已经访问过的节点
        Set<Vertex<V, E>> visitedVertices = new HashSet<>();
        Stack<Vertex<V, E>> stack = new Stack<>();

        // 访问第一个节点
        stack.push(beginVertex);
        visitedVertices.add(beginVertex);
        visitor.visit(beginVertex.value);

        while (!stack.isEmpty()) {
            Vertex<V, E> vertex = stack.pop();
            // 随便找出任意一条边
            for (Edge<V, E> edge : vertex.outEdges) {
                // 已经访问过了，就不再访问了
                if (visitedVertices.contains(edge.to)) continue;

                // 将该边的from和to都入栈
                stack.push(edge.from);
                stack.push(edge.to);

                // 访问
                visitedVertices.add(edge.to);
                visitor.visit(edge.to.value);
                break;
            }
        }
    }


    /**
     * 递归调用深度优先遍历
     *
     * @param vertex
     * @param visitedVertices 可以兼顾无向有环图。存储已经访问的节点，如果已经访问过就不再访问
     */
    private void dfs(Vertex<V, E> vertex, Set<Vertex<V, E>> visitedVertices) {
        // 访问节点
        System.out.println(vertex.value);
        // 访问过就存储起来
        visitedVertices.add(vertex);

        // 访问该节点下面的所有出去边(outEdges)的to节点
        for (Edge<V, E> edge : vertex.outEdges) {
            if (visitedVertices.contains(edge.to)) continue;
            // 递归调用
            dfs(edge.to, visitedVertices);
        }
    }
}
